package common.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 */
public class _438_FindAnagrams {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (s == null || p == null) {
            return ans;
        }
        int sLength = s.length();
        int pLength = p.length();
        if (sLength < pLength) {
            return ans;
        }
        char[] sAry = new char[26];
        char[] pAry = new char[26];
        for (int i = 0; i < pLength; i++) {
            sAry[s.charAt(i) - 'a']++;
            pAry[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sAry, pAry)) {
            ans.add(0);
        }
        for (int i = 1, j = pLength; i < sLength - pLength; i++, j++) {
            sAry[s.charAt(i) - 'a']--;
            sAry[s.charAt(j) - 'a']++;
            if (Arrays.equals(sAry, pAry)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }
}
